#include <atomic>
#include <memory>

template<typename T>
class LockFreeQueue {
private:
    struct Node {
        std::shared_ptr<T> data;
        std::atomic<Node*> next;
        
        Node() : next(nullptr) {}
    };
    
    std::atomic<Node*> head;
    std::atomic<Node*> tail;
    
    // 伪节点，简化实现
    Node* dummy_node;

public:
    LockFreeQueue() {
        dummy_node = new Node;
        head.store(dummy_node);
        tail.store(dummy_node);
    }
    
    ~LockFreeQueue() {
        while (Node* old_head = head.load()) {
            head.store(old_head->next);
            delete old_head;
        }
        delete dummy_node;
    }
    
    void enqueue(T new_value) {
        std::shared_ptr<T> new_data(std::make_shared<T>(new_value));
        Node* new_node = new Node;
        new_node->data.swap(new_data);
        
        Node* old_tail = tail.load();
        while (!tail.compare_exchange_weak(old_tail, new_node)) {
            // 循环重试
        }
        old_tail->next.store(new_node);
    }
    
    std::shared_ptr<T> dequeue() {
        Node* old_head = head.load();
        Node* old_tail = tail.load();
        Node* next = old_head->next.load();
        
        if (old_head == old_tail) { // 队列为空或只有一个元素
            if (!next) {
                return std::shared_ptr<T>(); // 队列为空
            }
            // 更新tail指针
            tail.compare_exchange_strong(old_tail, next);
        } else {
            std::shared_ptr<T> res = next->data;
            head.store(next);
            delete old_head;
            return res;
        }
        return std::shared_ptr<T>();
    }
};